package Top101K;

import netscape.security.UserTarget;

import java.util.Arrays;
import java.util.PriorityQueue;

import static a14_Sort.Demo2_QuickSort.quickSort;


/**
 * @Author quan
 * @Description 无序数组的中位数
 * @Date 2023/10/16 20:24
 */
public class a02_midNum {
    public static void main(String[] args) {
        //奇数个数字，返回最中间的一个；偶数个数字，返回中间两个数字的平均数
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        //方法1：暴力求解
//        int res  = fun1(arr);
        //方法2：快排思想
        System.out.println(fun2(arr));

    }

    /**
     * 快排思想：选择一个元素，满足其左边都是小于该数字的，右边都是大于该数字的，且左边的长度恰好是(n-1)/2，说明该元素就是中位数
     * @param arr
     * @return
     */
    public static double fun2(int[] arr) {
        int i = 0;
        int j = arr.length-1;
        int len = arr.length;
        //6-观察排序是否成功
        quickSort(arr,i,j);
        //如果长度是奇数，返回中间位置的值
        if(len%2==1){
            return (double)arr[len/2];
        }else{
            //说明是偶数，返回中间位置的两个数的平均值
            return (double)(arr[len/2]+arr[len/2-1])/2;
        }
    }

    public static void quickSort(int[] arr,int i,int j){
        int left = i;
        int right = j;
        //边界条件
        if(left>right){
            return;
        }
        //1-定义边界值
        int baseNum = arr[i];
        //2-开始循环
        // 找到左边第一个大于基准数的值
        while (left < right){
            //注意一定是先从右开始走，不然会报错！
            while (true){
                if(right <= left || arr[right] < baseNum){
                    break;
                }
                right--;
            }
            while (true){
                if(right<=left ||  arr[left] >baseNum){
                    break;
                }
                left++;
            }
            //3-交换两个位置的值
            swap(arr,left,right);
        }
        //4-基准数归位
        swap(arr,left,i);
        //5-递归的排序左区间
        //这里递归的时候，要用i和j来表示，不然会报错，因为每次递归的区间值是不同的。
        quickSort(arr,i,left-1);
        quickSort(arr,left+1,j);

    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /**
     * 暴力解法
     * @param arr
     * @return
     */
    public static int fun1(int[] arr){
        //排序
        Arrays.sort(arr);
        int len = arr.length;
        int mid = len/2;
        if(len % 2 == 0){
            //偶数
            return ((arr[mid]+arr[mid-1])/2);
        }else{
            return (arr[mid]);
        }
    }

}
